package jm.data.structure.union_find;

import jm.data.structure.hash.HashMap;
import jm.data.structure.map.Map;

import java.util.Objects;

/**
 * @Description 自定义类型union find
 * @date 2022/5/10 15:22
 */
public class UnionFindObj<V> {

    private Map<V, Node<V>> nodes = new HashMap<>();

    // 初始化集合
    public void makeSet(V v){
        if (nodes.containsKey(v))return;
        nodes.put(v, new Node<V>(v));
    }

    public V find(V v){
        Node<V> node = findNode(v);
        return node == null ? null : node.v;
    }

    /**
     * 找到 v 对应的根节点
     * @param v
     * @return
     */
    private Node<V> findNode(V v){
        // 当前 v 对应的节点
        Node<V> node = nodes.get(v);

        if (node == null) return null;

        // 如果当前节点与父节点的值不相同就不是根节点
        while (!Objects.equals(node.v,node.parent.v)){
            // 路径减半操作
            node.parent = node.parent.parent;
            node = node.parent;
        }

        return node;
    }

    public void union(V v1, V v2){
        Node<V> node1 = findNode(v1);
        Node<V> node2 = findNode(v2);
        if (node1 == null || node2 == null) return;
        if (Objects.equals(node1.v,node2.v)) return;

        if (node1.rank < node2.rank){
            node1.parent = node2;
        }else if (node1.rank > node2.rank){
            node2.parent = node1;
        }else {
            node1.parent = node2;
            node2.rank += 1;
        }

    }

    public boolean isSame(V v1, V v2){
        return Objects.equals(find(v1),find(v2));
    }

    private static class Node<V>{
        V v;
        // 创建节点时parent指向自己
        Node<V> parent = this;
        int rank = 1;
        public Node(V v) {
            this.v = v;
        }
    }
}
